SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Cache-oblivious algorithm</title>

</head>

Cache-oblivious algorithm

</h1>

</header>

In <a href="Computing" title="Computing">computing</a>, a cache-oblivious algorithm (or cache-transcendent algorithm) is an <a href="Algorithm" title="Algorithm">algorithm</a> designed to take advantage of a processor <a href="CPU_cache" title="CPU cache">cache</a> without having the size of the cache (or the length of the <a href="Cache_line" class="mw-redirect" title="Cache line">cache lines</a>, etc.) as an explicit parameter. An optimal cache-oblivious algorithm is a cache-oblivious algorithm that uses the cache optimally (in an <a href="Asymptotic_notation" class="mw-redirect" title="Asymptotic notation">asymptotic</a> sense, ignoring constant factors). Thus, a cache-oblivious algorithm is designed to perform well, without modification, on multiple machines with different cache sizes, or for a <a href="Memory_hierarchy" title="Memory hierarchy">memory hierarchy</a> with different levels of cache having different sizes. Cache-oblivious algorithms are contrasted with explicit <a href="Loop_tiling" class="mw-redirect" title="Loop tiling">loop tiling</a>, which explicitly breaks a problem into blocks that are optimally sized for a given cache.

Optimal cache-oblivious algorithms are known for <a href="Cache-oblivious_matrix_multiplication" class="mw-redirect" title="Cache-oblivious matrix multiplication">matrix multiplication</a>, <a href="Matrix_transposition" class="mw-redirect" title="Matrix transposition">matrix transposition</a>, <a href="Funnelsort" title="Funnelsort">sorting</a>, and several other problems. Some more general algorithms, such as <a href="Cooley%E2%80%93Tukey_FFT_algorithm" title="Cooley–Tukey FFT algorithm">Cooley–Tukey FFT</a>, are optimally cache-oblivious under certain choices of parameters. As these algorithms are only optimal in an asymptotic sense (ignoring constant factors), further machine-specific <a href="Performance_tuning" title="Performance tuning">tuning</a> may be required to obtain nearly optimal performance in an absolute sense. The goal of cache-oblivious algorithms is to reduce the amount of such tuning that is required.

Typically, a cache-oblivious algorithm works by a <a href="Recursion" title="Recursion">recursive</a> <a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">divide-and-conquer algorithm</a>, where the problem is divided into smaller and smaller subproblems. Eventually, one reaches a subproblem size that fits into the cache, regardless of the cache size. For example, an optimal cache-oblivious matrix multiplication is obtained by recursively dividing each matrix into four sub-matrices to be multiplied, multiplying the submatrices in a <a href="Depth-first" class="mw-redirect" title="Depth-first">depth-first</a> fashion. In tuning for a specific machine, one may use a <a href="Hybrid_algorithm" title="Hybrid algorithm">hybrid algorithm</a> which uses loop tiling tuned for the specific cache sizes at the bottom level but otherwise uses the cache-oblivious algorithm.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

The idea (and name) for cache-oblivious algorithms was conceived by <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a> as early as 1996 and first published by <a href="Harald_Prokop" title="Harald Prokop">Harald Prokop</a> in his master's thesis at the <a href="Massachusetts_Institute_of_Technology" title="Massachusetts Institute of Technology">Massachusetts Institute of Technology</a> in 1999.<a href="#cite_note-Prokop-1">[1]</a> There were many predecessors, typically analyzing specific problems; these are discussed in detail in Frigo et al. 1999. Early examples cited include Singleton 1969 for a recursive Fast Fourier Transform, similar ideas in Aggarwal et al. 1987, Frigo 1996 for matrix multiplication and LU decomposition, and Todd Veldhuizen 1996 for matrix algorithms in the <a href="Blitz%2B%2B" title="Blitz++">Blitz++</a> library.

<div class="mw-heading mw-heading2"><h2 id="Idealized_cache_model">Idealized cache model</h2></div>

In general, a <a href="Computer_program" title="Computer program">program</a> can be made more cache-conscious:<a href="#cite_note-nick05-2">[2]</a>

<ul><li><a href="Locality_of_reference#Types_of_locality" title="Locality of reference">Temporal locality</a>, where the algorithm fetches the same pieces of memory multiple times;</li>

<li>Spatial locality, where the subsequent memory accesses are adjacent or nearby <a href="Memory_address" title="Memory address">memory addresses</a>.</li></ul>

Cache-oblivious algorithms are typically analyzed using an idealized model of the cache, sometimes called the cache-oblivious model. This model is much easier to analyze than a real cache's characteristics (which have complex associativity, replacement policies, etc.), but in many cases is provably within a constant factor of a more realistic cache's performance. It is different than the <a href="External_memory_model" class="mw-redirect" title="External memory model">external memory model</a> because cache-oblivious algorithms do not know the <a href="Block_(data_storage)" title="Block (data storage)">block size</a> or the <a href="Cache_(computing)" title="Cache (computing)">cache</a> size.

In particular, the cache-oblivious model is an <a href="Abstract_machine" title="Abstract machine">abstract machine</a> (i.e., a theoretical <a href="Model_of_computation" title="Model of computation">model of computation</a>). It is similar to the <a href="RAM_model" class="mw-redirect" title="RAM model">RAM machine model</a> which replaces the <a href="Turing_machine" title="Turing machine">Turing machine</a>'s infinite tape with an infinite array. Each location within the array can be accessed in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> time, similar to the <a href="Random-access_memory" title="Random-access memory">random-access memory</a> on a real computer. Unlike the RAM machine model, it also introduces a cache: the second level of storage between the RAM and the CPU. The other differences between the two models are listed below. In the cache-oblivious model:

<ul><li>Memory is broken into blocks of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

<li>A load or a store between <a href="Main_memory" class="mw-redirect" title="Main memory">main memory</a> and a CPU register may now be serviced from the cache.</li>

<li>If a load or a store cannot be serviced from the cache, it is called a cache miss.</li>

<li>A cache miss results in one block being loaded from the main memory into the cache. Namely, if the CPU tries to access word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is the line containing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is loaded into the cache. If the cache was previously full, then a line will be evicted as well (see replacement policy below).</li>

<li>The cache holds <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M=\Omega (B^{2})}</annotation>

</semantics>

</math><img src="./d4da530f0265309181bcc8b7f23396d4e90973af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.846ex; height:3.176ex;" alt="{\displaystyle M=\Omega (B^{2})}" loading="lazy">. This is also known as the tall cache assumption.</li>

<li>The cache is fully associative: each line can be loaded into any location in the cache.<a href="#cite_note-Kumar-3">[3]</a></li>

<li>The replacement policy is optimal. In other words, the cache is assumed to be given the entire sequence of memory accesses during algorithm execution. If it needs to evict a line at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">, it will look into its sequence of future requests and evict the line whose first access is furthest in the future. This can be emulated in practice with the <a href="Least_Recently_Used" class="mw-redirect" title="Least Recently Used">Least Recently Used</a> policy, which is shown to be within a small constant factor of the offline optimal replacement strategy<a href="#cite_note-Frigo99-4">[4]</a><a href="#cite_note-Sleator-5">[5]</a></li></ul>

To measure the complexity of an algorithm that executes within the cache-oblivious model, we measure the number of <a href="Cache_miss" class="mw-redirect" title="Cache miss">cache misses</a> that the algorithm experiences. Because the model captures the fact that accessing elements in the <a href="Cache_(computing)" title="Cache (computing)">cache</a> is much faster than accessing things in <a href="Main_memory" class="mw-redirect" title="Main memory">main memory</a>, the <a href="Running_time" class="mw-redirect" title="Running time">running time</a> of the algorithm is defined only by the number of memory transfers between the cache and main memory. This is similar to the <a href="External_memory_model" class="mw-redirect" title="External memory model">external memory model</a>, which all of the features above, but cache-oblivious algorithms are independent of cache parameters (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">).<a href="#cite_note-Demaine02-6">[6]</a> The benefit of such an algorithm is that what is efficient on a cache-oblivious machine is likely to be efficient across many real machines without fine-tuning for particular real machine parameters. For many problems, an optimal cache-oblivious algorithm will also be optimal for a machine with more than two <a href="Memory_hierarchy" title="Memory hierarchy">memory hierarchy</a> levels.<a href="#cite_note-Frigo99-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

The simplest cache-oblivious algorithm presented in Frigo et al. is an out-of-place <a href="Matrix_transpose" class="mw-redirect" title="Matrix transpose">matrix transpose</a> operation (<a href="In-place_matrix_transposition" title="In-place matrix transposition">in-place algorithms</a> have also been devised for transposition, but are much more complex for non-square matrices). Given m×n array A and n×m array B, we would like to store the transpose of A in B. The naive solution traverses one array in row-major order and another in column-major. The result is that when the matrices are large, we get a cache miss on every step of the column-wise traversal. The total number of cache misses is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (mn)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (mn)}</annotation>

</semantics>

</math><img src="./3869811594f411c0d4025ba7b8e5f8069b436cf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.053ex; height:2.843ex;" alt="{\displaystyle \Theta (mn)}" loading="lazy">.

The cache-oblivious algorithm has optimal work complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn)}</annotation>

</semantics>

</math><img src="./89ea09572a098b4762141a22c43a7ba1c20051cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.018ex; height:2.843ex;" alt="{\displaystyle O(mn)}" loading="lazy"> and optimal cache complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1+mn/B)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1+mn/B)}</annotation>

</semantics>

</math><img src="./1fce18c6ce32ba203ab12883c1d6a15e17eccc5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.947ex; height:2.843ex;" alt="{\displaystyle O(1+mn/B)}" loading="lazy">. The basic idea is to reduce the transpose of two large matrices into the transpose of small (sub)matrices. We do this by dividing the matrices in half along their larger dimension until we just have to perform the transpose of a matrix that will fit into the cache. Because the cache size is not known to the algorithm, the matrices will continue to be divided recursively even after this point, but these further subdivisions will be in cache. Once the dimensions m and n are small enough so an input array of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\times n}</annotation>

</semantics>

</math><img src="./12b23d207d23dd430b93320539abbb0bde84870d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.276ex; height:1.676ex;" alt="{\displaystyle m\times n}" loading="lazy"> and an output array of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\times m}</annotation>

</semantics>

</math><img src="./d82325a2a02ad79bc7c347ba9702ad46eb0de824.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.276ex; height:1.676ex;" alt="{\displaystyle n\times m}" loading="lazy"> fit into the cache, both row-major and column-major traversals result in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn)}</annotation>

</semantics>

</math><img src="./89ea09572a098b4762141a22c43a7ba1c20051cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.018ex; height:2.843ex;" alt="{\displaystyle O(mn)}" loading="lazy"> work and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn/B)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn/B)}</annotation>

</semantics>

</math><img src="./7367d86cb3534e5f7c6699be93f0f3b99a324b09.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.944ex; height:2.843ex;" alt="{\displaystyle O(mn/B)}" loading="lazy"> cache misses. By using this divide and conquer approach we can achieve the same level of complexity for the overall matrix.

(In principle, one could continue dividing the matrices until a base case of size 1×1 is reached, but in practice one uses a larger base case (e.g. 16×16) in order to <a href="Amortized_analysis" title="Amortized analysis">amortize</a> the overhead of the recursive subroutine calls.)

Most cache-oblivious algorithms rely on a divide-and-conquer approach. They reduce the problem, so that it eventually fits in cache no matter how small the cache is, and end the recursion at some small size determined by the function-call overhead and similar cache-unrelated optimizations, and then use some cache-efficient access pattern to merge the results of these small, solved problems.

Like <a href="External_sorting" title="External sorting">external sorting</a> in the <a href="External_memory_model" class="mw-redirect" title="External memory model">external memory model</a>, cache-oblivious sorting is possible in two variants: <a href="Funnelsort" title="Funnelsort">funnelsort</a>, which resembles <a href="Mergesort" class="mw-redirect" title="Mergesort">mergesort</a>; and <a href="Cache-oblivious_distribution_sort" title="Cache-oblivious distribution sort">cache-oblivious distribution sort</a>, which resembles <a href="Quicksort" title="Quicksort">quicksort</a>. Like their external memory counterparts, both achieve a <a href="Running_time" class="mw-redirect" title="Running time">running time</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}">

<mrow>

<mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msub>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</msub>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}</annotation>

</semantics>

</math><img src="./496ff85a291f2a81b89ac3b14929c774ad5c0035.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:16.713ex; height:6.343ex;" alt="{\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}" loading="lazy">, which matches a <a href="Lower_bound" class="mw-redirect" title="Lower bound">lower bound</a> and is thus <a href="Asymptotically_optimal" class="mw-redirect" title="Asymptotically optimal">asymptotically optimal</a>.<a href="#cite_note-Demaine02-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="Practicality">Practicality</h2></div>

An empirical comparison of 2 RAM-based, 1 cache-aware, and 2 cache-oblivious algorithms implementing <a href="Priority_queue" title="Priority queue">priority queues</a> found that:<a href="#cite_note-7">[7]</a>

<ul><li>Cache-oblivious algorithms performed worse than RAM-based and cache-aware algorithms when data fits into main memory.</li>

<li>The cache-aware algorithm did not seem significantly more complex to implement than the cache-oblivious algorithms, and offered the best performance in all cases tested in the study.</li>

<li>Cache oblivious algorithms outperformed RAM-based algorithms when data size exceeded the size of main memory.</li></ul>

Another study compared <a href="Hash_table" title="Hash table">hash tables</a> (as RAM-based or cache-unaware), <a href="B-tree" title="B-tree">B-trees</a> (as cache-aware), and a cache-oblivious data structure referred to as a "Bender set". For both execution time and memory usage, the hash table was best, followed by the B-tree, with the Bender set the worst in all cases. The memory usage for all tests did not exceed main memory. The hash tables were described as easy to implement, while the Bender set "required a greater amount of effort to implement correctly".<a href="#cite_note-8">[8]</a>

<ul><li><a href="Cache-oblivious_distribution_sort" title="Cache-oblivious distribution sort">Cache-oblivious distribution sort</a></li>

<li><a href="External_memory_algorithm" title="External memory algorithm">External memory algorithm</a></li>

<li><a href="Funnelsort" title="Funnelsort">Funnelsort</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-Prokop-1"><a href="#cite_ref-Prokop_1-0">^</a> Harald Prokop. <a rel="nofollow" class="external text" href="http://supertech.csail.mit.edu/papers/Prokop99.pdf">Cache-Oblivious Algorithms</a>. Masters thesis, MIT. 1999.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAskitisZobel2005" class="citation book cs1">Askitis, Nikolas; Zobel, Justin (2005). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/11575832_11">"Enhanced Byte Codes with Restricted Prefix Properties"</a>. String Processing and Information Retrieval. Lecture Notes in Computer Science. Vol. 3772. <a href="Springer_Publishing" title="Springer Publishing">Springer</a>. p. 93. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11575832_1">10.1007/11575832_1</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-29740-6</bdi>.</cite> <code class="cs1-code">{{cite book}}</code>: <code class="cs1-code">|journal=</code> ignored (help)

</li>

<li id="cite_note-Kumar-3"><a href="#cite_ref-Kumar_3-0">^</a> <cite id="CITEREFKumar" class="citation journal cs1">Kumar, Piyush. "Cache-Oblivious Algorithms". Algorithms for Memory Hierarchies. LNCS 2625. Springer Verlag: 193–212. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.5426">10.1.1.150.5426</a>.</cite>

</li>

<li id="cite_note-Frigo99-4">^ <a href="#cite_ref-Frigo99_4-0">a</a> <a href="#cite_ref-Frigo99_4-1">b</a> <cite id="CITEREFFrigoLeisersonProkopRamachandran1999" class="citation conference cs1">Frigo, M.; <a href="Charles_Leiserson" class="mw-redirect" title="Charles Leiserson">Leiserson, C. E.</a>; <a href="Harald_Prokop" title="Harald Prokop">Prokop, H.</a>; Ramachandran, S. (1999). <a rel="nofollow" class="external text" href="http://supertech.csail.mit.edu/papers/FrigoLePr99.pdf">Cache-oblivious algorithms</a> (PDF). Proc. IEEE Symp. on Foundations of Computer Science (FOCS). pp. 285–297.</cite>

</li>

<li id="cite_note-Sleator-5"><a href="#cite_ref-Sleator_5-0">^</a> Daniel Sleator, Robert Tarjan. <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.367.6317&rep=rep1&type=pdf">Amortized Efficiency of List Update and Paging Rules</a>. In Communications of the ACM, Volume 28, Number 2, pp. 202–208. Feb 1985.

</li>

<li id="cite_note-Demaine02-6">^ <a href="#cite_ref-Demaine02_6-0">a</a> <a href="#cite_ref-Demaine02_6-1">b</a> <a href="Erik_Demaine" title="Erik Demaine">Erik Demaine</a>. <a rel="nofollow" class="external text" href="http://erikdemaine.org/papers/BRICS2002/">Cache-Oblivious Algorithms and Data Structures</a>, in Lecture Notes from the EEF Summer School on Massive Data Sets, BRICS, University of Aarhus, Denmark, June 27–July 1, 2002.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFOlsenSkov2002" class="citation thesis cs1">Olsen, Jesper Holm; Skov, Søren Christian (2 December 2002). <a rel="nofollow" class="external text" href="http://hjemmesider.diku.dk/~jyrki/PE-lab/Publications/olsen-skov02.pdf">Cache-Oblivious Algorithms in Practice</a> (PDF) (Master's). University of Copenhagen. Retrieved 3 January 2022.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFVerver2008" class="citation web cs1">Verver, Maks (23 June 2008). <a rel="nofollow" class="external text" href="https://fmt.ewi.utwente.nl/media/61.pdf">"Evaluation of a Cache-Oblivious Data Structure"</a> (PDF). Retrieved 3 January 2022.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-11-03" href="https://en.wikipedia.org/wiki/?title=Cache-oblivious_algorithm&oldid=1255108940">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>